package algorthm.systemTraning.dynamicPlanning;
import util.RandomUtil;

import java.util.*;

public class HJ16{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
//        int N = RandomUtil.randIntRange(4, 100 ,  8000);
//        int m = RandomUtil.randIntRange(2, 4 ,  15); ;
        int N = in.nextInt();
        int m = in.nextInt();
        List<Product> products = new ArrayList();
//        if(in.hasNextInt()) { // 注意 while 处理多个 case
//            N = in.nextInt();
//            m = in.nextInt();
//        }
        for(int a = 1 ; a <= m ; a++){
//            int price = RandomUtil.randIntRange(4, 50 ,  8000);
//            int importance = RandomUtil.randIntRange(3, 10 ,  30);
//            int amount = RandomUtil.randIntRange(2, 5,  15);
//            int parent = 0 ;
//            if(amount < a){
//                parent = a - RandomUtil.randIntRange(2, 0 ,a);
//            }
            products.add(new Product(a , in.nextInt() , in.nextInt() , in.nextInt()));
        }
        int[][] value = new int[products.size()][3];
        int[][] price = new int[products.size()][3];
        List<Product> main = component(value , price , products);
//        for (int i = 0; i < 100; i++) {
        int[][] dp = new int[main.size()][N+1];
        int[][] dp1 = new int[main.size()][N+1];
            int p1 = maxSatisfiedSocre(N , main , value , price , dp);
            int p2 = maxSatisfiedSocre2(N , main , value , price , dp1);
            for(int a = 0 ; a < dp.length ; a++){
                for (int i = 0; i < dp[a].length; i++) {
                    if(dp[a][i] != 0 &&dp[a][i] != dp1[a][i]){
                        System.out.println("error: x , y => " + a + " ," + i + " and "
                                + " dp , dp1 => " + dp[a][i] + " , " + dp1[a][i]
                        );
                    }
                }

            }
            System.out.println("p1 = " + p1 + " p2 = " + p2);
            if(p1 != p2){
                System.out.println("error , list :" + Arrays.deepToString(products.toArray()));
//            }
        }
    }
    public static  List<Product> component(int[][] value , int[][] price , List<Product> products){
        List<Product> main = new ArrayList();
        int j = 0 ;
        for(int i = 0 ; i < products.size() ; i++){
            if(products.get(i).q == 0){
                main.add(products.get(i));
                value[j][0] = products.get(i).p;
                price[j][0] = products.get(i).v;
                List<Product> c = getFj(products.get(i).idx , products);
                if(c.size() > 0){
                    value[j][1] = c.get(0).p;
                    price[j][1] = c.get(0).v;
                    if(c.size() > 1 ){
                        value[j][2] = c.get(1).p;
                        price[j][2] = c.get(1).v;
                    }
                }
                j++;
            }
        }
        return main ;
    }
    public static List<Product> getFj(int id , List<Product> products){
        List<Product> rs = new ArrayList<Product>();
        for(int i = 0 ; i < products.size() ; i++){
            if(id == products.get(i).q){
                rs.add(products.get(i));
            }
        }
        return rs ;
    }
    // public static int maxSatisfiedSocre(List<Product> list , int startIdx , int endIdx , int N){
    //     int score = list.get(startIdx).v*list.get(startIdx).p ;
    //     int subScore = maxSatisfiedSocre(list , startIdx - 1 , endIdx , N);
    //     if
    // }
    public static class Product{
        public int idx ;
        public int v ;
        public int p ;
        public int q ;
        public Product(int idx ,int v , int p , int q){
            this.idx = idx ;
            this.v = v ;
            this.p = p ;
            this.q = q ;
        }

        @Override
        public String toString() {
            return "Product{" +
                    "idx=" + idx +
                    ", v=" + v +
                    ", p=" + p +
                    ", q=" + q +
                    '}';
        }
    }
    public static int maxSatisfiedSocre(int N ,List<Product> products , int[][] value , int[][] price , int[][] dp){
        if(N == 0 || null == products || products.size() == 0) return 0 ;
//        int[][] dp = new int[products.size()][N+1];
        int p = process(0, N, products, value, price, dp);
        System.out.println("maxSatisfiedSocre: dp");
        for(int i = 0 ; i < dp.length ; i++){
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println("");
        }
        return p;
    }

    public static int maxSatisfiedSocre2(int N ,List<Product> products , int[][] value , int[][] price , int[][] dp){
        if(N == 0 || null == products || products.size() == 0) return 0 ;
//        int[][] dp = new int[products.size()][N+1];
        int p1 = -1 ;
        int p2 = -1 ;
        int p3 = -1 ;
        int p4 = -1 ;
        int idx = products.size()-1 ;
        // int j = N ;
        for(int j = N ; j >= products.get(idx).v ; j-- ){
            p1 = -1 ;
            p2 = -1 ;
            p3 = -1 ;
            p4 = -1 ;
            if( j >= products.get(idx).v){
                p1 = products.get(idx).v*products.get(idx).p ;
                // dp[idx][j - products.get(idx).v] = p1 ;
            }

            if(j >= products.get(idx).v + price[idx][1]){
                p2 = products.get(idx).v*products.get(idx).p + value[idx][1]*price[idx][1] ;
                // dp[idx][j - products.get(idx).v - price[idx][1]] = p2 ;
            }

            if(j >= products.get(idx).v + price[idx][2]){
                p3 = products.get(idx).v*products.get(idx).p + value[idx][2]*price[idx][2] ;
                // dp[idx][j - products.get(idx).v - price[idx][2]] = p3 ;
            }

            if(j >= products.get(idx).v + price[idx][1] + price[idx][2]){
                p4 = products.get(idx).v*products.get(idx).p + value[idx][1]*price[idx][1] + value[idx][2]*price[idx][2] ;
                // dp[idx][j - products.get(idx).v - price[idx][1] - price[idx][2]] = p4 ;
            }
            dp[idx][j] = Math.max(Math.max(p1 , p2) , Math.max(p3 , p4));
        }
        int p5 = 0 ;
        for(int i = products.size() - 2 ; i>=0  ; i--){
            // j 应该是 > 0 ，不能是 j > products.get(i).v , > i 的那些物品可能小于 j 这样也能返回值
            for(int j = N ; j > 0 ; j--){
                p1 = -1 ;
                p2 = -1 ;
                p3 = -1 ;
                p4 = -1 ;
                p5 = -1 ;
                // 不要 i
                p5 = dp[i+1][j];
                if( j >= products.get(i).v ){
                    p1 = products.get(i).v*products.get(i).p + dp[i+1][j - products.get(i).v];
                    // dp[i][j - products.get(i).v] = p1 ;
                }
                if(j >= products.get(i).v + price[i][1]){
                    p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + dp[i+1][j - products.get(i).v - price[i][1]];
                    // dp[i][j - products.get(i).v - price[i][1]] = p2;
                }
                if(j >= products.get(i).v + price[i][2]){
                    p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] + dp[i+1][j - products.get(i).v - price[i][2]];
                    // dp[i][j - products.get(i).v - price[i][2]] = p3 ;

                }
                if(j >= products.get(i).v + price[i][1] + price[i][2]){
                    p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] + dp[i+1][j - products.get(i).v - price[i][1] - price[i][2]];
                    // dp[i][j - products.get(i).v - price[i][1] - price[i][2] ] = p4 ;
                }
                dp[i][j] = Math.max(Math.max(p1 , p2) , Math.max(Math.max(p3 , p4) , p5));
            }
        }
        System.out.println("maxSatisfiedSocre1: dp");
        for(int i = 0 ; i < dp.length ; i++){
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println("");
        }
        return dp[0][N];
    }

    /**
     i 物品开始得位置，-1 代表所有的构件类型。
     N 是总钱数
     id 是查找物品的 id
     product 是物品列表。
     */
    public static int process(int i , int N , List<Product> products , int[][] value , int[][] price , int[][] dp){
        if(i + 1 == products.size()){
            int p1 =0 ;
            int p2 =0 ;
            int p3 =0 ;
            int p4 =0 ;
            if( N >= products.get(i).v){
                p1 = products.get(i).v*products.get(i).p ;
            }
            if(N >= products.get(i).v + price[i][1]){
                p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] ;
            }
            if(N >= products.get(i).v + price[i][2]){
                p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] ;
            }
            if(N >= products.get(i).v + price[i][1] + price[i][2]){
                p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] ;
            }
            if(N <= 0){
                return -1 ;
            }else{
                dp[i][N] =  Math.max(Math.max(p1 , p2) , Math.max(p3 , p4));
            }
            return dp[i][N];
        }
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int p4 = 0;
        // 只要 i 的作为主键
        int next = process(i+1 , N - products.get(i).v , products , value , price , dp);
        if(-1 == next){
            next = 0 ;
        }
        if( N >= products.get(i).v ){
            p1 = products.get(i).v*products.get(i).p + next ;
        }
        if(N >= products.get(i).v + price[i][1]){
            next = process(i+1 , N - products.get(i).v - price[i][1] , products , value , price ,dp);
            if(-1 == next){
                next = 0 ;
            }
            p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + next ;
        }
        if(N >= products.get(i).v + price[i][2]){
            next = process(i+1 , N - products.get(i).v - price[i][2] , products , value , price , dp);
            if(-1 == next){
                next = 0 ;
            }
            p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] + next;
        }
        if(N >= products.get(i).v + price[i][1] + price[i][2]){
            next = process(i+1 , N - products.get(i).v - price[i][1] - price[i][2] , products , value , price , dp);
            if(-1 == next){
                next = 0 ;
            }
            p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] + next;
        }
        // 不要 i
        int p5 = process(i+1 , N , products , value , price , dp);
        if(N <= 0){
            return -1 ;
        }else{
            dp[i][N] = Math.max(Math.max(p1 , p2) , Math.max(p5 , Math.max(p3 , p4)));
        }
        return dp[i][N];
    }
}